/*
Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region .

For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X
*/

class Solution {
public:
    void solve(vector<vector<char> > &board) {
        m = board.size();
        if (!m) return;
        n = board[0].size();
        if (!n) return;
        for (int i = 0; i < m; i++) { bfs(i, 0, board); bfs(i, n-1, board); }
        for (int j = 1; j < n-1; j++) { bfs(0, j, board); bfs(m-1, j, board); }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == 'V') board[i][j] = 'O';
            }
        }
        return;
    }
private: 
    int m, n;
    void bfs(int i, int j, vector<vector<char> >&board) {
        queue<int> bfsq;
        visit(i, j, bfsq, board);
        while (!bfsq.empty()) {
            int num = bfsq.front();
            int x = num/n, y = num%n;
            visit(x-1, y, bfsq, board);
            visit(x+1, y, bfsq, board);
            visit(x, y-1, bfsq, board);
            visit(x, y+1, bfsq, board);
            bfsq.pop();
        }
    }
    void visit(int i, int j, queue<int> &bfsq, vector<vector<char> >&board) {
        if (i < 0 || i >=m || j < 0 || j>=n || board[i][j] != 'O') return;
        board[i][j] = 'V';
        bfsq.push(i*n + j);
    }
};

#if 0
class Solution {
public:
    void solve(vector<vector<char> > &board) {
        m = board.size();
        if (!m) return;
        n = board[0].size();
        if (!n) return;
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') dfs(0, j, board);
            if (board[m-1][j] == 'O') dfs(m-1, j, board);
        }
        for (int i = 1; i < m-1; i++) {
            if (board[i][0] == 'O') dfs(i, 0, board);
            if (board[i][n-1] == 'O') dfs(i, n-1, board);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == 'V') board[i][j] = 'O';
            }
        }
        return;
    }
    void dfs(int i, int j, vector<vector<char> >&board) {
        //if (i < 0 || i >= m || j < 0 || j >=n) return;
        board[i][j] = 'V';  // mark as visited
        if (i-1 >=0 && board[i-1][j] == 'O') dfs(i-1, j, board);
        if (i+1 < m && board[i+1][j] == 'O') dfs(i+1, j, board);
        if (j-1 >=0 && board[i][j-1] == 'O') dfs(i, j-1, board);
        if (j+1 < n && board[i][j+1] == 'O') dfs(i, j+1, board);
    }
private:
    int m, n;
};
#endif
